import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * LeetCode 15. 三数之和
 */
public class Solution_15 {
    /**
     * 排序 + 双指针
     * <p>
     * 排序后固定一个数 nums[i]，再使用左右指针指向 nums[i] 后面的两端，
     * 
     * 数字分别为 nums[left] 和 nums[right]，计算三个数的和 sum 判断是否满足为 0
     * <p>
     * 时间复杂度：排序 O(nlogn) + 双层循环 O(n^2) --> O(n^2)
     * <p>
     * 空间复杂度：O(logn)，排序
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        // 对数组进行排序
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            // 若 nums[i] > 0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
            if (nums[i] > 0) {
                return ans;
            }
            // 对于重复元素：跳过，避免出现重复解
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 左右指针
            int left = i + 1, right = len - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] > 0) {
                    // 若和大于 0，right 左移，减小和
                    right--;
                } else if (nums[i] + nums[left] + nums[right] < 0) {
                    // 若和小于 0，left 右移，增大和
                    left++;
                } else {
                    // 符合条件的三元组添加到结果
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去除重复解
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
        return ans;
    }
}
